# 找到当前所在位置的，且确定方向后的最佳步长，有以下方法
# met1；解析解法
#       求f(xk + akdk)对ak的偏导，偏导

# met2：数值解法
#       step1: 先确定ak所在的搜索区间，该区间应是一维函数极小点在内的单谷区间[a, b]
#              注：单谷区间是 函数在这个区间内处处有定义
#                 且 在这个区间内  只有唯一极小值
#       step2: 然后根据区间消去原理在[a, b]内不断缩小此区间,
# 区间消去原理说明：
# 在step1给出的初始搜索区间[a, b]
# 在这个区间内任取两点a1, b1, 其中a < a1 < b1 < b
# 选取a1, b1的方法有
# Met1: 黄金分割法
# case1:
#     f(a1) < f(b1)
#     极小点在[a, b1]上
# case2:
#     f(a1) > f(b1)
#     极小点在[a1, b]上
# case3:
#     f(a1) = f(b1)
#     极小点在[a1, b1]上

# 对于met2 的 step1
# 可使用确定搜索区间的外推法
# 目标：
# 找到一个区间[a, b], 和一个点c, 使得f(a) >= f(c) 且 f(b) >= f(c)
# 单谷区间内

# 用黄金分割法求函数的极小点，
# 给定初始搜索点x0 = 0，搜索步长h = 1, 误差精度要求e = 0.2
# 引入math模块，其中的pow函数可以实现幂次运算
import math


# 确定目标函数因变量取值的函数
def objFun(x):
    y = 3 * math.pow(x, 3.0) - 4.0 * x + 2.0
    return y


def maxValue(x, y):
    if x > y:
        return x
    else:
        return y


def minValue(x, y):
    if x > y:
        return y
    else:
        return x


def oriInterval():
    x1 = 0
    h1 = 1
    y1 = objFun(x1)
    x2 = x1 + h1
    y2 = objFun(x2)
    if y1 > y2:
        h = 2 * h1
        x3 = x1 + h
        y3 = objFun(x3)
        while y2 > y3:
            x3 = x1 + h
            y3 = objFun(x3)
            if y2 > y3:
                h = 2 * h
                x1 = x2
                x2 = x3
        return minValue(x1, x3), maxValue(x1, x3)
    if y1 < y2:
        h = -2 * h1
        x3 = x1 + h
        y3 = objFun(x3)
        while y2 > y3:
            x3 = x1 + h
            y3 = objFun(x3)
            if y2 > y3:
                h = 2 * h
                x1 = x2
                x2 = x3
        return minValue(x1, x3), maxValue(x1, x3)
    if y1 == y2:
        return x1, x2


# 确定初始搜索区间
ret = oriInterval()
print(f'初始搜索区间为：{ret}')

e = 0.2

a = ret[0]
b = ret[1]
print(ret[0])
print(ret[1])
a1 = a + (1 - 0.618) * (b - a)
b1 = a + 0.618 * (b - a)

y1 = objFun(a1)
y2 = objFun(b1)


while (b - a) > e:
    if y1 < y2:
        b = b1
        b1 = a1
        y2 = y1
        a1 = a + (1 - 0.618) * (b - a)
        y1 = objFun(a1)
    else:
        a = a1
        a1 = b1
        y1 = y2
        b1 = a + 0.618 * (b - a)
        y2 = objFun(b1)

midRet = 0.5 * (a + b)
retValue = objFun(midRet)

print(f'最小点是{midRet}, 最小值是{retValue}')

